Convergent sequences of sparse graphs: A large deviations approach

Models based on sparse graphs are of interest to many communities: they appear as basic models in combinatorics, probability theory, optimization, statistical physics, information theory, and more applied fields of social sciences and economics. Different notions of similarity (and hence convergence) of sparse graphs are of interest in different communities. In probability theory and combinatorics, the notion of Benjamini‐Schramm convergence, also known as left‐convergence, is used quite frequently. Statistical physicists are interested in the the existence of the thermodynamic limit of free energies, which leads naturally to the notion of right‐convergence. Combinatorial optimization problems naturally lead to so‐called partition convergence, which relates to the convergence of optimal values of a variety of constraint satisfaction problems. The relationship between these different notions of similarity and convergence is, however, poorly understood. In this paper we introduce a new notion of convergence of sparse graphs, which we call Large Deviations or LD‐convergence, and which is based on the theory of large deviations. The notion is introduced by “decorating” the nodes of the graph with random uniform i.i.d. weights and constructing corresponding random measures on and . A graph sequence is defined to be converging if the corresponding sequence of random measures satisfies the Large Deviations Principle with respect to the topology of weak convergence on bounded measures on . The corresponding large deviations rate function can be interpreted as the limit object of the sparse graph sequence. In particular, we can express the limiting free energies in terms of this limit object. We then establish that LD‐convergence implies the other three notions of convergence discussed above, and at the same time establish several previously unknown relationships between the other notions of convergence. In particular, we show that partition‐convergence does not imply left‐ or right‐convergence, and that right‐convergence does not imply partition‐convergence. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 52–89, 2017     

Constructing near spanning trees with few local inspections

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let G be a connected bounded‐degree graph. Given an edge e in G we would like to decide whether e belongs to a connected subgraph consisting of edges (for a prespecified constant ), where the decision for different edges should be consistent with the same subgraph . Can this task be performed by inspecting only a constant number of edges in G ? Our main results are:

• We show that if every t‐vertex subgraph of G has expansion then one can (deterministically) construct a sparse spanning subgraph of G using few inspections. To this end we analyze a “local” version of a famous minimum‐weight spanning tree algorithm.
• We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of 3‐regular graphs of high girth, in which every t‐vertex subgraph has expansion . We prove that for this family of graphs, any local algorithm for the sparse spanning graph problem requires inspecting a number of edges which is proportional to the girth.

© 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 183–200, 2017     

Hypergeometric approach to Apéry-like series

By reformulating four hypergeometric series formulae, we derive 36 Apéry-like series expressions for the Riemann zeta function, including a couple of identities conjectured by Sun [New series for some special values of L-functions. Nanjing Univ J Math. 2015;32(2): 189–218].     

SiOx encapsulated FeSi2–Si eutectic nanoparticles as durable anode of lithium-ion batteries

Low-cost and high-efficiency production of silicon-based material is the key to improve the energy density of lithium-ion batteries. Herein, we propose a novel structure of FeSi₂–Si eutectic nanoparticles protected by the SiO_x shell. FeSi₂, as a buffer phase can improve the electrochemical stability of the electrode. A SiO_x shell is formed on the surface of the nanoparticles through the passivation process. SiO_x encapsulated FeSi₂–Si eutectic nanoparticles exhibit excellent capacity of 674.9 mAh/g after 500 charge/discharge cycles. The capacity retention rate is above 90% after the stabilization process. This work provides a new nanomaterial design for high performance silicon-based anode materials of lithium-ion batteries.     

Secondary-flow-aided single-train elastic-inertial focusing in low elasticity viscoelastic fluids

Elastic-inertial focusing has attracted increasing interest in recent years due to the three-dimensional (3D) single-train focusing ability it offers. However, multi-train focusing, instead of single-train focusing, was observed in viscoelastic fluids with low elasticity as a result of the competition between inertia effect and viscoelasticity effect. To address this issue, we employed the secondary flow to facilitate single-train elastic-inertial focusing in low elasticity viscoelastic fluids. A three-section contraction-expansion channel was designed to induce the secondary flow to pinch the multiplex focusing trains into a single one exactly at the channel centerline. After demonstrating the focusing process and mechanism in our device, we systematically explored and discussed the effects of particle diameter, operational flow rate, polymer concentration, and channel dimension on particle focusing performances. Our device enables single-train focusing of particles in viscoelastic fluids with low elasticity, and offers advantages of planar single-layer structure, and sheathless, external-field free operation.     

Several improved asymptotic normality criteria and their applications to graph polynomials

As widely regarded, one of the most classical and remarkable tools to measure the asymptotic normality of combinatorial statistics is due to Harper's real-rooted method proposed in 1967. However, this classical theorem exists some obvious shortcomings, for example, it requests all the roots of the corresponding generating function, which is impossible in general.Aiming to overcome this shortcoming in some extent, in this paper we present an improved asymptotic normality criterion, along with several variant versions, which usually just ask for one coefficient of the generating function, without knowing any roots. In virtue of these new criteria, the asymptotic normality of some usual combinatorial statistics can be revealed and extended. Among which, we introduce the applications to matching numbers and Laplacian coefficients in detail. Some relevant conjectures, proposed by Godsil (Combinatorica, 1981) and Wang et al. (J. Math. Anal. Appl., 2017), are generalized and verified as corollaries.     

Exceptional Laurent biorthogonal polynomials through spectral transformations of generalized eigenvalue problems

A formulation is given for the spectral transformation of the generalized eigenvalue problem through the decomposition of the second-order differential operators. This allows us to construct some Laurent biorthogonal polynomial systems with gaps in the degree of the polynomial sequence. These correspond to an exceptional-type extension of the orthogonal polynomials, as an extension of the Laurent biorthogonal polynomials. Specifically, we construct the exceptional extension of the Hendriksen–van Rossum polynomials, which are biorthogonal analogs of the classical orthogonal polynomials. Similar to the cases of exceptional extensions of classical orthogonal polynomials, both state-deletion and state-addition occur.     

Computer-assisted analysis of chaos in a three-species food chain model

In this paper, a three-species food chain model with Holling type IV and Beddington–DeAngelis functional responses is formulated. Numerical simulations show that this system can generate chaos for some parameter values. But the mechanism behind chaos is still unclear only through numerical simulations. Then, using the topological horseshoe theories and Conley–Moser conditions, we present a computer-assisted analysis to show the chaoticity of this system in the topological sense, that is, it has positive topological entropy. We prove that the Poincaré map of this model possesses a closed uniformly hyperbolic chaotic invariant set, and it is topologically conjugate to a 2-shift map. At last, we consider the impact of fear on this three-species model. It is an important factor in controlling chaos in biological models, which has been validated in other models.